信息的表示和处理

三种最重要的数字表示：

无符号编码：基于传统的二进制表示，表示大于或者等于0的数。
补码编码：表示有符号整数的最常见的方式，有符号整数就是可以为正或者为负的元素。
浮点数编码：表示浮点数的科学计数法以二为基数的版本。

计算机的表示法会产生一些问题：

范围是有限的，当超过时就会发生溢出（overflow）。
整数满足运算性质（结合律，交互律等），浮点数不满足。

本节主要介绍计算机中对数的编码和运算

信息存储

大部分计算机使用8位为一块，称为字节，作为最小的访问单位。
机器级程序将内存视为一个非常大的字节数组，称为虚拟内存。内存的每个字节都是由哦一个唯一的数字来标识，称为地址。所有可能的虚拟地址的集合称为虚拟地址空间。

十六进制表示法

二进制太长，十进制不好转换成二进制，最好的方式是用十六进制来表示数。
二进制与十六进制之间的转换比较简单，其它进制转换为十进制用幂乘法，十进制转其它进制用模运算。

字数据大小

字长：指针数据的大小，决定了虚拟地址空间的最大大小。

有符号	无符号	32位	64位
{signed} char	unsigned char	1	1
shrot	unsigned short	2	2
int	unsigned	4	4
long	unsigned long	4	8
int32_t	uint32_t	4	4
int64_t	uint64_t	8	8
char *		4	8
float		4	4
double		8	8

上表是C基本数据类型的典型大小，注意事项：

char一般不区分符号
ISO C99引入了一类数据类型，不依赖“典型”数据大小和编译器环境，其中包括int32_t和int64_t。
对关键词的顺序以及是否省略可选关键词，C允许存在多种形式。

寻址和字节顺序

位：[xn,…x1]
xn为最高有效位，x1为最低有效位。转换成字节（为8的倍数时）对应最高有效字节，和最低有效字节。
小端法：在地址中有效字节从低到高。大端法相反。

字节顺序会影响的问题时：

当传输和接受网络数据时
当阅读数据类型的字节序列时
当使用强制类型转型时

字符串的表示

每一个字符都由标准字符编码来表示，最常见的是ASCII表。
使用ASCII表来进行编码的文件成为文本文件，其他的成为二进制文件。在使用ASCII编码的系统中，文本文件比二进制文件具有更强的平台独立性，因为不受字节顺序和字大小的约束。

布尔代数简介

用于处理真和假，0和1的逻辑运算。拓展到多个就叫做位向量，位向量一个很实用的作用是用来表示有限的集合，以及很方便的做集合之间的交，并，补。

C语言中的布尔运算，逻辑运算，移位运算

布尔：|，&，~，^
逻辑：||，&&，!
移位运算：<<，>>，>>>（java）

对于左移运算，在低位补0.对于右移运算，一般都有逻辑右移（高位补0）和算术右移（高位补和最高有效位相同的数），对于确切的是哪一种，没有明确定义。但是，一般来说，对于有符号的数据，采用算术右移；无符号的采取逻辑右移。而在java中，明确表示>>表示算术右移；>>>表示逻辑右移。

当移动的数大于数据本身的位数时，C语言会报错，而在java中要求采取模运算的方式来处理移动的位数。

整数表示

无符号编码和补码只是两种二进制编码方式
对于补码而言，只是数字所表示的含义不同，是为了给计算机定义“负数”所采用的一种方式，但是它是符合正常的加减法规则的，因此在作计算时无需考虑其含义。

符号	类型	含义
$B2T_{w}$	函数	二进制转补码
$B2U_{w}$	函数	二进制转无符号
$U2B_{w}$	函数	无符号转二进制
$U2T_{w}$	函数	无符号转补码
$T2B_{w}$	函数	补码转二进制
$T2U_{w}$	函数	补码转无符号
$TMin_{w}$	常数	最小补码值
$TMax_{w}$	常数	最大补码值
$UMax_{w}$	常数	最大无符号值
$+_{t}^{w}$	操作	补码加
$+_{u}^{w}$	操作	无符号加
$* _{t}^{w}$	操作	补码乘
$* _{u}^{w}$	操作	无符号乘
$-_{t}^{w}$	操作	补码减
$-_{t}^{w}$	操作	无符号减

有符号的数和无符号的数之间存在隐式或者显式的转换。尤其注意在逻辑运算时，这种隐式的转换会带来一些非直观的效果，导致程序出现异常。

无符号的编码

$B2U_{w}(\overrightarrow{x})=\sum_{i=0}^{w-1}x_{i}2^{i}$

补码编码

$B2T_{w}(\overrightarrow{x})=-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_{i}2^{i}$

无符号与补码之间的转换

首先，我们必须认清楚一个概念，就是无符号和补码之间的转换是以相同的二进制码为基础的不同的表示方法之间的转换，通过上面的补码和无符号的两个公司我们可以得到：

$B2T_{w}(\overrightarrow{x})=-x_{w-1}2^{w}+B2U_{w}(\overrightarrow{x})$

补码转无符号

$T2U_{w}(x)=B2U_{w}(T2B_{w}(x))=x_{w-1}2^{w}+x$

在补码范围内的非负数，对应的无符号一致；负数对应的无符号需要增加一个步长。

无符号转补码

为补码转无符号公式的反函数：

$U2T_{w}(u)=-u_{w-1}2^{w}+u$

在无符号范围内的小于补码最大值的数，对应的补码一致；大于补码最大值的数对应的无符号减少增加一个步长。

位的扩展和截断

扩展：

补码在开头补符号位
无符号在开头补0.

截断：
截断可以解释为先转换成无符号码进行模运算，再转成成对应的编码表示。

无符号： $B2U_{k}(u)[x_{k-1},x_{k-2},...,x_{0}]=B2U_{w}(w)[x_{w-1},x_{w-2},...,x_{0}]mod2^{k}$
补码： $B2U_{k}(u)[x_{k-1},x_{k-2},...,x_{0}]=U2T_{k}(B2U_{w}(w)[x_{w-1},x_{w-2},...,x_{0}]mod2^{k})$

整数运算

无符号加法

在无符号的值范围内可以正常相加，当有溢出时，溢出的位截断，只保留定常的位。公式如下：
$x+_{u}^{w}y=\begin{cases} & x+y\text{ if } x+y<2^{w} \\ & x+y-2^{w}\text{ if } x+y>=2^{w} \end{cases}$

一般来说，当程序发生溢出，并不会报错，因此需要人为的去进行判断，判断的方法是：对x+y=s，若s<x，则发生溢出。

模运算是一个阿贝尔群，因此满足交换律，结合律，并有一个单位元，且有逆元。公式如下：
$-_{u}^{w}x=\begin{cases} & x\text{ if } x=0 \\ & 2^{w}-x\text{ if } x>0 \end{cases}$

补码加法

无论是无符号加法还是补码加法或者是其它加法，在计算机底层都是同一种二进制的加法，而二进制的加法可以表现成无符号加法，因此补码的加法可以表现为先转换成无符号进行加法运算，截断后再转换成补码公式如下:

对于补码加法的正溢出，可以理解为最高符号位上的0变成了1，因此从正数变成了负数，然后转补码（此时需要减去一个位长值）。
对于补码加法的负溢出，可以理解为在位之外多了一个1，截断即为做了模运算，然后转补码（此时不需要减去位长值，但是模运算的时候也相当于加上了位长值）。

补码的溢出判断

对于x+y=s，当x>0，y>0时，s<=0，发生了正溢出。当x<0，y<0时，s>=0，发生了负溢出。

乘法

首先我们得知道，对于无符号和有符号的底层乘法实现方式是不一样的，具体是如何可以参考其他的书籍，在C语言中，w位的整数相乘后可能需要2w位来进行表示，而有符号和无符号被定义为相应的2w位二进制截断w位后的不同编码方式。而对它们来说，2w位的二进制可能不一样，但是截断后的w位恰巧都是相同的，这也就是所谓的乘法的位级表示是一样的，表示成定义即：给定位向量 $\vec{x}$ 和位向量 $\vec{y}$ ,他们的补码表示为x和y，无符号表示为x’和y’，因而有：
$T2B_{w}(x*_{w}^{t}y)=U2B_{w}(x'*_{w}^{u}y')$
在理解乘法公式之前，先提出模运算具有的一个性质： $(x\cdot y)mod2^w=(x'\cdot y')mod2^w$

无符号的乘法公式： $x*_{w}^{u}y=(x\cdot y)mod2^w$
补码的乘法公式： $x*_{w}^{t}y=U2T_{w}((x\cdot y)mod2^w)$

一开始对补码公式一直乘法不太理解，后来才明白，这样的表示，其实就是结合上面模运算的性质，先进性无符号的运算，再将无符号转换成补码。

乘一个常数

整数的乘法指令速度相当慢，需要10个或者更多的时钟周期，而其它的运算只需要一个。因而对于乘一个常数，我们往往用移位来实现。

乘2的幂：无论是无符号还是补码，乘2的k次方等价于左移k位，发生溢出导致的结果也一样。
乘任意常数：如14=2^3+2^2+2，因此，x*2^14可以用(x<<3)+(x<<2)+(x<<1)来实现。

除一个2的幂

计算机中的除法是向下舍入正数值，向上舍入负数值，在使用右移来实现除2的幂时需要注意，因为右移只能产生向下舍入的结果，对于负数的向上舍入，需要先加上一个偏量，再做右移操作。

无符号的除以2的k次幂：x>>k。
补码的除以2的k次幂：(x<0?x+(1<<k)-1:x)>>k

浮点数

定点表示法

定点整数：纯整数，小数点定在最低有效位后。
定点小数：纯小数，小数点定在符号位之后，最高有效位之前。
定点浮点数：需要一个比例因子先转换成定点小数或者定点整数，运算后再根据比例因子还原成实际结果。比例因子的选择不当，往往会造成溢出或者降低有效精度。

IEEE浮点表示法

公式： $V=(-1)^{s}*M*2^{E}$

s：符号，对于0的符号作位特殊情况处理。
M：尾数，二进制数,f为其二进制表示的小数,M=f或者是1+f。
E：阶码，2的E次幂。

对于32位机器来说，s长1,M长8,E长23。对于64位的机器来说，s长1，M长11，E长52.

浮点表示法

值分成三种情况

规格化的值：阶码位不全为0或者1，这种情况下，M=1+f，阶码字段被解释为以偏置形式来表示有符号整数，也就是说阶码值E=e-Bias，其中e是无符号值，Bias是偏置值等于2^k-1-1（单精度127，双精度1023）由此产生的指数的取值范围：单精度：-126~127.双精度：-1022~1023.
非规格化的值：阶码位全为0，这种情况下，E=1-Bias，M=f。非规格化的值提供两个功能：①提供+0和-0的表示②提供了接近0的值均匀分布。
特殊值：阶码位全为1时。若尾数位全为0，根据符号表示正无穷或负无穷。若尾数位不全为0，表示NaN.

浮点表示法

三种情况的分布区域

浮点表示法

案例：

浮点表示法

舍入

偶数舍入：对于中间值，向偶数舍入，在小数舍入时，尤其要确认该小数是否中间值。
向零舍入：绝对值变小。
向上舍入：上确界。
向下舍入：下确界。

浮点运算

Round(x?Y)，满足交换律，不满足结合律，具备单调性。
这里书中也没有很具体，需要从其它地方获取详细的过程。

C语言的浮点数

C提供两种浮点是，float和double且大多情况下支持IEEE标准，但C并没有强制要求符合IEEE标准，因此并没有标准方法改变舍入方式或者定义诸如-0, +∞+∞, −∞−∞或者NaN这些特殊值，大多数系统提供相应头文件或库，但没有统一标准，可能细节有所不同。

强制转换的规则：

从int到float，数字不会溢出，但可能被舍入。
从int/float转到double，因double精度更大，因此能保留精确的数值。
从double到float，可能溢出成为 ±∞±∞，也有可能因精度问题被舍入
从float/double转为int，值将向零舍入。进一步说，值可能会溢出（毕竟浮点数范围更大）。然而，C标准没有对此的规定。因此，有些诸如与Intel兼容的微处理器将整数最小值统一定义为整数不确定（integer indefinite）值，即溢出结果。例如对于32位数，TMin_32 = [10…000] = -2^31 = 2 147 483 648。

常用的移位运算

数据位长：

1	sizeof(date)<<3（字节长×8个位）

溢出判断：

t = a + b时，如果a，b异号（或者存在0），则肯定不会溢出。
如果a，b均大于等于0，则t<0就是正溢出，如果a，b均小于0，则t>=0就是负溢出。
于是，可以利用三个变量来表示是正溢出，负溢出还是无溢出。
int w = sizeof(int)<<3;
int t = x + y;
int ans = x + y;
x>>=(w-1);//11111111
y>>=(w-1);//11111111
t>>=(w-1);//00000000
int pos_ovf = ~x&~y&t;//00000000
int neg_ovf = x&y&~t;//11111111
int novf = ~(pos_ovf|neg_ovf);//00000000

对于有符号整数相减，溢出的规则可以总结为：
t = a-b;
如果a, b 同号，则肯定不会溢出。
如果a>=0 && b<0，则只有当t<=0时才算溢出。
如果a<0 && b>=0，则只有当t>=0时才算溢出。
不过，上述t肯定不会等于0，因为当a，b不同号时：
1) a!=b，因此a-b不会等于0。
2) a-b <= abs(a) + abs(b) <= abs(TMax) + abs(TMin)=(2^w - 1)
所以，a，b异号，t，b同号即可判定为溢出。
int tsub_ovf(int x, int y){
    int w = sizeof(int)<<3;
    int t = x - y;
    x>>=(w-1);
    y>>=(w-1);
    t>>=(w-1);
    return (x != y) && (y == t);
}